package code.oldCode.feishuSpecializedTraining.greedy;

/**
 * @author 26029
 * @date 2025/3/19
 * @description
 */
public class MyGreedy2 {
    // 122. 买卖股票的最佳时机 II
    public int maxProfit(int[] prices) {
        // 贪心做法：找所有上升的部分
        if (prices == null || prices.length <= 1)
            return 0;
        int len = prices.length;
        int count = 0;
        for (int i = 1; i < len; i++) {
            int diff = prices[i] - prices[i - 1];
            if (diff > 0)
                count += diff;
        }
        return count;
    }

    public int maxProfit_dp(int[] prices) {
        // dp做法：经典股票问题的可多次购买的情况，两个数组，分别代表在当前点购买和在当前点抛出
        if (prices == null || prices.length == 0)
            return 0;
        int len = prices.length;
        int[] have = new int[len]; // have[i] = max(noHave[i-1] - prices[i], have[i-1])
        int[] noHave = new int[len]; // noHave[i] = max(have[i-1] + prices[i], noHave[i-1])
        have[0] = -prices[0];
        noHave[0] = 0;
        for (int i = 1; i < len; i++) {
            have[i] = Math.max(noHave[i - 1] - prices[i], have[i - 1]);
            noHave[i] = Math.max(have[i - 1] + prices[i], noHave[i - 1]);
        }
        return noHave[len - 1];
    }

    // 55. 跳跃游戏
    public boolean canJump(int[] nums) {
        // 贪心做法：不断更新可以到达的最远距离
        int len = nums.length;
        int farest = 0;
        for (int i = 0; i < len; i++) {
            if (i > farest)
                return false;
            int now = i + nums[i];
            farest = Math.max(farest, now);
        }
        return true;
    }

    // 45. 跳跃游戏 II
    public int jump(int[] nums) {
        // 贪心：遍历的时候确定最远能到哪，到达target（除了到头）之后，代表走了一步，更新下一个target
        // （题目保证可以到达最后）
        int len = nums.length;
        int step = 0;
        int target = 0;
        int farest = 0;
        for (int i = 0; i < len; i++) {
            farest = Math.max(farest, i + nums[i]);
            // 到达target后，step+1（代表继续往后走了），确定下一个target，如果是最后一个，就不往后加了
            if (i == target && i != len - 1) {
                target = farest;
                step++;
            }
        }
        return step;
    }
}
